package club.vann.nowcoder;

import java.util.PriorityQueue;

/**
 * <p>难度：Easy</p>
 * <p>题目：合并两个有序数组</p>
 * <p>描述：给出两个有序的整数数组 和 ，请将数组 合并到数组 中，变成一个有序的数组
 * 注意：
 * 可以假设 数组有足够的空间存放 数组的元素， 和 中初始的元素数目分别为 和 </p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-18:19:21:23
 */
public class NC22 {
    public static void main(String[] args) {
        NC22 nc22 = new NC22();

        nc22.merge1(TestCase.A, TestCase.M, TestCase.B, TestCase.N);
        System.out.println("Success");
    }

    /**
     * 解法一：
     *
     * @param A
     * @param m
     * @param B
     * @param n
     */
    public void merge(int A[], int m, int B[], int n) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0; i < m; i ++) {
            queue.add(A[i]);
        }

        for(int i = 0; i < n; i ++) {
            queue.add(B[i]);
        }

        int i = 0;
        while(!queue.isEmpty()) {
            A[i++] = queue.poll();
        }
    }

    /**
     * 解法二：
     *
     * @param A
     * @param m
     * @param B
     * @param n
     */
    public void merge1(int A[], int m, int B[], int n) {
        int indexA = m-1, indexB = n-1, index = m+n-1;
        while(indexA >= 0 || indexB >= 0) {
            if (indexA >= 0 && indexB >= 0) {
                if(A[indexA] >= B[indexB]) {
                    A[index] = A[indexA];
                    indexA --;
                } else {
                    A[index] = B[indexB];
                    indexB --;
                }
            } else if(indexA >= 0){
                A[index] = A[indexA];
                indexA --;
            } else {
                A[index] = B[indexB];
                indexB --;
            }
            index --;
        }
    }

    static class TestCase {
        public static int[] A = {6,7,8,9,10,0,0,0};
        public static int[] B = {1,2,3};
        public static int M = 5;
        public static int N = 3;
    }
}
